package cn.xkai.exercise.a;

import java.util.Arrays;

/**
 * @description: 最长公共前缀
 * 自己的思路：先找出最小的串，然后循环对最小串进行startwith判断，不符合则最小串减少尾部1个字符，直到通过所有判断
 * 借鉴的思路：先给定一个默认前缀，如果以该串开头则继续查找，否则匹配2个串直接最小公共前缀
 * 心得：借鉴的思路更简洁，退出逻辑更清晰
 * @author: kaixiang
 * @date: 2022-06-23
 **/
public class Solution8 {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1) {
            return strs[0];
        }
        String prefix = "";
        int min = 200;
        for (String str : strs) {
            if (str.length() < min) {
                min = str.length();
            }
        }
        boolean skip = true;
        while (min > 0) {
            prefix = strs[0].substring(0, min);
            for (String str : strs) {
                if (!str.startsWith(prefix)) {
                    skip = false;
                    min--;
                    break;
                }
                skip = true;
            }
            if (min <= 0) {
                prefix = "";
            }
            if (skip) {
                break;
            }
        }
        return prefix;
    }

    public String longestCommonPrefixRefer(String[] strs) {
        String prefix = strs[0];
        for (String s : strs) {
            if (prefix.startsWith(s)) {
                prefix = s;
                continue;
            }
            for (int i = 0; i < prefix.length(); i++) {
                if (s.charAt(i) != prefix.charAt(i)) {
                    prefix = new String(Arrays.copyOf(prefix.toCharArray(), i));
                    break;
                }
            }
        }
        return prefix;
    }

    public static void main(String[] args) {
        String[] strs = {"ab", "a"};
        Solution8 solution8 = new Solution8();
        System.out.println(solution8.longestCommonPrefix(strs));
    }
}
